// 在一个由 '0' 和 '1' 组成的二维矩阵内，
// 找到只包含 '1' 的最大正方形，并返回其面积。

/**
 * @param {string[][]} matrix
 * @return {number}
 */
var maximalSquare = function (matrix) {
  const m = matrix.length
  const n = matrix[0].length

  const dp = new Array(m).fill(0).map(() => new Array(n).fill(0))

  for (let i = 0; i < m; i++) {
    dp[i][0] = parseInt(matrix[i][0], 10)
  }
  for (let i = 0; i < n; i++) {
    dp[0][i] = parseInt(matrix[0][i], 10)
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (matrix[i][j] === '0') {
        continue
      }
      dp[i][j] = Math.min(
        dp[i - 1][j],
        dp[i][j - 1],
        dp[i - 1][j - 1]
      ) + 1
    }
  }

  let len = 0
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      len = Math.max(dp[i][j], len)
    }
  }

  return len * len
}

console.log(
  maximalSquare([["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"]])
)